package 代码随想录.回溯.组合总和;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class LeetCode39 {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(candidates);
//        backtracking(res,new ArrayList<>(),candidates,target,0,0);
        backtracking1(res, new ArrayList<>(), candidates, target, 0, 0);
        return res;
    }

    /**
     * @param res        存放结果集
     * @param path       存放符合条件的结果
     * @param candidates 集合
     * @param target     目标值
     * @param sum        统计单一结果里path的总和
     * @param idx        控制for循环的起始位置
     */
    public void backtracking(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) {
        if (sum == target) {    //找到了和为target的组合
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = idx; i < candidates.length; i++) {
            //如果sum+candidates[i]>target 就终止遍历
            if (sum + candidates[i] > target) break;
            path.add(candidates[i]);
            //这里最后一个传入i，是因为本层里面的元素在下一层依然可以重复使用，需要思考
            backtracking(res, path, candidates, target, sum + candidates[i], i);
            path.remove(path.size() - 1); //回溯，移除路径path最后一个元素
        }
    }

    //未剪枝的版本
    public void backtracking1(List<List<Integer>> res, List<Integer> path, int[] candidates, int target, int sum, int idx) {
        if (sum > target) {
            return;
        }
        if (sum == target) {    //找到了和为target的组合
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = idx; i < candidates.length; i++) {
            path.add(candidates[i]);
            backtracking1(res, path, candidates, target, sum + candidates[i], i);
            path.remove(path.size() - 1); //回溯，移除路径path最后一个元素
        }
    }

    public static void main(String[] args) {
        int[] candidates = {2, 3, 6, 7};
        int target = 7;
        LeetCode39 code = new LeetCode39();
        System.out.println(code.combinationSum(candidates, target));
    }
}
